package wtx.geek;

import java.util.*;
import java.util.Random;

/**
 * Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

 Example 1:

 Input: "babad"
 Output: "bab"
 Note: "aba" is also a valid answer.
 Example 2:

 Input: "cbbd"
 Output: "bb"
 */
public class Solution {
  private static int searchLeftRight(String s, int left, int sum) {
    int right = sum - left;
    final int N = s.length();
    while(left >= 0 && right < N && s.charAt(left) == s.charAt(right) ) {
      --left;
      ++right;
    }
    return left+1;
  }
  public static String longestPalindrome(String s) {
    if (s == null || s.length() == 0) {
      return "";
    }
    int longestPalinSubString = 0;
    int leftLongest = 0;
    final int N = s.length();
    for (int i = 0; i < N; ++i) {
      int sum = 2*i+1;
      int left = searchLeftRight(s, i, sum);
      int len = sum - 2 * left + 1;
      int sum2 = sum - 1;
      int left2 = searchLeftRight(s, i, sum2);
      int len2 = sum2 - 2*left2 + 1;
      if (len < len2) {
        len = len2;
        left = left2;
      }
      if (longestPalinSubString < len) {
        longestPalinSubString = len;
        leftLongest = left;
      }
    }
    return s.substring(leftLongest, longestPalinSubString + leftLongest);
  }
  public static void main(String[] args) {
    String a = "babad";
    System.out.println(longestPalindrome(a));
  }
}
